{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Edit Distance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minDistance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #编辑距离"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个单词&nbsp;<code>word1</code> 和&nbsp;<code>word2</code>， <em>请返回将&nbsp;<code>word1</code>&nbsp;转换成&nbsp;<code>word2</code> 所使用的最少操作数</em> &nbsp;。</p>\n",
    "\n",
    "<p>你可以对一个单词进行如下三种操作：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>插入一个字符</li>\n",
    "\t<li>删除一个字符</li>\n",
    "\t<li>替换一个字符</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>word1 = \"horse\", word2 = \"ros\"\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>\n",
    "horse -&gt; rorse (将 'h' 替换为 'r')\n",
    "rorse -&gt; rose (删除 'r')\n",
    "rose -&gt; ros (删除 'e')\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>word1 = \"intention\", word2 = \"execution\"\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>\n",
    "intention -&gt; inention (删除 't')\n",
    "inention -&gt; enention (将 'i' 替换为 'e')\n",
    "enention -&gt; exention (将 'n' 替换为 'x')\n",
    "exention -&gt; exection (将 'n' 替换为 'c')\n",
    "exection -&gt; execution (插入 'u')\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= word1.length, word2.length &lt;= 500</code></li>\n",
    "\t<li><code>word1</code> 和 <code>word2</code> 由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [edit-distance](https://leetcode.cn/problems/edit-distance/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [edit-distance](https://leetcode.cn/problems/edit-distance/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"horse\"\\n\"ros\"', '\"intention\"\\n\"execution\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, sa: str, sb: str) -> int:\n",
    "        d = [[0] * (len(sb) + 1) for _ in range(len(sa) + 1)]\n",
    "        for i in range(len(sa) + 1):\n",
    "            d[i][0] = i\n",
    "        for i in range(len(sb) + 1):\n",
    "            d[0][i] = i\n",
    "        for i, a in enumerate(sa, 1):\n",
    "            for j, b in enumerate(sb, 1):\n",
    "                if a == b:\n",
    "                    d[i][j] = d[i - 1][j - 1]\n",
    "                else:\n",
    "                    d[i][j] = min(d[i - 1][j] + 1, d[i - 1][j - 1] + 1, d[i][j - 1] + 1)\n",
    "        return d[-1][-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1, word2):\n",
    "        \"\"\"\n",
    "        :type word1: str\n",
    "        :type word2: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        m = len(word1)\n",
    "        n = len(word2)\n",
    "        a = list(range(n + 1))\n",
    "        b = list(range(n + 1))\n",
    "        for i in range(m + 1):\n",
    "            for j in range(n + 1):\n",
    "                if i == 0:\n",
    "                    b[j] = j\n",
    "                    continue\n",
    "                if j == 0:\n",
    "                    b[j] = i\n",
    "                    continue\n",
    "                l = min(a[j], b[j - 1], a[j - 1]) + 1\n",
    "                if word1[i - 1] == word2[j - 1]:\n",
    "                    l = min(l, a[j - 1])\n",
    "                b[j] = l\n",
    "            a, b = b, a\n",
    "        return a[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1, word2):\n",
    "        \"\"\"\n",
    "        :type word1: str\n",
    "        :type word2: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        d = [i for i in range(len(word1)+2)]\n",
    "        \n",
    "        for i in range(1,len(word2)+1):\n",
    "            pre = d[0]\n",
    "            d[0] = i #这个更新很重要\n",
    "            # print(d)\n",
    "            for j in range(1,len(word1)+1):\n",
    "                tmp = d[j]\n",
    "                if word2[i-1] == word1[j-1]:\n",
    "                    d[j] = pre\n",
    "                else:\n",
    "                    d[j] = min(pre,min(d[j],d[j-1]))+1\n",
    "                pre = tmp\n",
    "            \n",
    "        return d[len(word1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1, word2):\n",
    "        \"\"\"\n",
    "        :type word1: str\n",
    "        :type word2: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        cur = list(range(len(word1) + 1))\n",
    "\n",
    "        for j, s in enumerate(word2):\n",
    "            last, cur = cur, [j+1]\n",
    "            for i, t in enumerate(word1):\n",
    "                cur.append(last[i] if s==t else min(last[i+1], last[i], cur[-1]) + 1)\n",
    "        return cur[-1]\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1, word2):\n",
    "        \"\"\"\n",
    "        :type word1: str\n",
    "        :type word2: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        result = [{} for _ in range(len(word1))]\n",
    "\n",
    "        def getDistance(index1, index2):\n",
    "            if index1 == len(word1): return len(word2) - index2\n",
    "            if index2 == len(word2): return len(word1) - index1\n",
    "            if index2 in result[index1]: return result[index1][index2]\n",
    "\n",
    "            s1, s2 = word1[index1:], word2[index2:]\n",
    "            distance = max(len(s1), len(s2))\n",
    "            for i in range(len(s1)):\n",
    "                if i >= distance: break\n",
    "                for j in range(len(s2)):\n",
    "                    if j >= distance: break\n",
    "                    if s1[i] == s2[j]:\n",
    "                        count = max(i, j) + getDistance(i + 1 + index1, j + 1 + index2)\n",
    "                        if count < distance: distance = count\n",
    "            result[index1][index2] = distance\n",
    "            return distance\n",
    "\n",
    "        return getDistance(0, 0)\n",
    "        \n",
    "  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1, word2):\n",
    "        \"\"\"\n",
    "        :type word1: str\n",
    "        :type word2: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        result = [{} for _ in range(len(word1) + 1)]\n",
    "\n",
    "        def getDistance(i, j):\n",
    "            if i == 0: return j\n",
    "            if j == 0: return i\n",
    "            if j in result[i]: return result[i][j]\n",
    "\n",
    "            if word1[i - 1] == word2[j - 1]:\n",
    "                distance = getDistance(i - 1, j - 1)\n",
    "            else:\n",
    "                distance = min(getDistance(i - 1, j - 1),\n",
    "                              getDistance(i - 1, j),\n",
    "                              getDistance(i, j - 1)) + 1\n",
    "            result[i][j] = distance\n",
    "            return distance\n",
    "\n",
    "        return getDistance(len(word1), len(word2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1, word2):\n",
    "        \"\"\"\n",
    "        :type word1: str\n",
    "        :type word2: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        l1,l2,tmp = len(word1),len(word2),[]\n",
    "        for i in range(l1+1):tmp.append([-1]*(l2+1))\n",
    "        return self.myMethod(word1, word2, l1, l2, tmp)\n",
    "    def myMethod(self, word1, word2, l1, l2, tmp):\n",
    "        if l1 == 0: return l2\n",
    "        if l2 == 0:return l1\n",
    "        if tmp[l1][l2] != -1:\n",
    "            return tmp[l1][l2]\n",
    "        \n",
    "        if word1[l1-1] == word2[l2-1]:\n",
    "            res = self.myMethod(word1,word2, l1-1, l2-1, tmp)\n",
    "        else:\n",
    "            res = min(self.myMethod(word1,word2, l1-1, l2-1, tmp),\n",
    "                     min(self.myMethod(word1, word2, l1 - 1, l2, tmp),\n",
    "                        self.myMethod(word1, word2, l1, l2 - 1, tmp))) + 1\n",
    "        tmp[l1][l2] = res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: 'str', word2: 'str') -> 'int':\n",
    "        # l1 = len(word1) + 1\n",
    "        # l2 = len(word2) + 1\n",
    "        # if l2 > l1:\n",
    "        #     return self.minDistance(word2,word1)\n",
    "        # m = [0]*l2  # 遍历到底i行时m[i]表示s1[:i-1]替换为s2[:j-1]的编辑距离\n",
    "        # for i in range(1,l2):\n",
    "        #     m[i] = i\n",
    "        # p = 0 # 用于存储上一行左上角的值\n",
    "        # for i in range(1, l1):\n",
    "        #     p = m[0]\n",
    "        #     m[0] = i\n",
    "        #     for j in range(1, l2):\n",
    "        #         tmp = m[j] # 先将上一行i处的结果存起来\n",
    "        #         m[j] = p if word1[i-1] == word2[j-1] else min(m[j-1] + 1, m[j] + 1, p + 1)\n",
    "        #         p = tmp\n",
    "        # return m[l2-1]\n",
    "        # l1 = len(word1) + 1\n",
    "        # l2 = len(word2) + 1\n",
    "        # if l2 > l1:\n",
    "        #     return self.minDistance(word2,word1)\n",
    "        # m = {}  # 遍历到底i行时m[i]表示s1[:i-1]替换为s2[:j-1]的编辑距离\n",
    "        # for i in range(0,l2):\n",
    "        #     m[i] = i\n",
    "        # p = 0 # 用于存储上一行左上角的值\n",
    "        # for i in range(1, l1):\n",
    "        #     p = m[0]\n",
    "        #     m[0] = i\n",
    "        #     for j in range(1, l2):\n",
    "        #         tmp = m[j] # 先将上一行i处的结果存起来\n",
    "        #         m[j] = p if word1[i-1] == word2[j-1] else min(m[j-1] + 1, m[j] + 1, p + 1)\n",
    "        #         p = tmp\n",
    "        # return m[l2-1]\n",
    "        d = {}\n",
    "        def helper(a, b):\n",
    "            if a * b == 0:\n",
    "                return a + b\n",
    "            if (a,b) not in d:\n",
    "                if word1[a-1] == word2[b-1]:\n",
    "                    d[a,b] = helper(a-1, b-1)\n",
    "                else:\n",
    "                    d[a,b] = 1 + min(helper(a-1, b), helper(a,b-1), helper(a-1,b-1))\n",
    "            return d[a,b]\n",
    "        return helper(len(word1), len(word2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1, word2):\n",
    "        \"\"\"\n",
    "        :type word1: str\n",
    "        :type word2: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        m = len(word1)\n",
    "        n = len(word2)\n",
    "        table = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "\n",
    "        for i in range(m + 1):\n",
    "            table[i][0] = i\n",
    "        for j in range(n + 1):\n",
    "            table[0][j] = j\n",
    "\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if word1[i - 1] == word2[j - 1]:\n",
    "                    table[i][j] = table[i - 1][j - 1]\n",
    "                else:\n",
    "                    table[i][j] = 1 + min(table[i - 1][j], table[i][j - 1], table[i - 1][j - 1])\n",
    "        return table[-1][-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: 'str', word2: 'str') -> 'int':\n",
    "        word1 = word1[::-1]\n",
    "        word2 = word2[::-1]\n",
    "        if word1 == \"\" and word2 == \"\":\n",
    "            return 0\n",
    "        if word1 == \"\":\n",
    "            return len(word2)\n",
    "        if word2 == \"\":\n",
    "            return len(word1)\n",
    "        DP = []\n",
    "        for i in range(len(word1) + 1):\n",
    "            tmp = []\n",
    "            for j in range(len(word2) + 1):\n",
    "                tmp.append(0)\n",
    "            DP.append(tmp)\n",
    "        \n",
    "        for i in range(len(word1) + 1):\n",
    "            for j in range(len(word2) + 1):\n",
    "                if i == 0:\n",
    "                    DP[i][j] = j\n",
    "                else:\n",
    "                    if j == 0:\n",
    "                        DP[i][j] = i\n",
    "                    else:\n",
    "                        if word1[i - 1] == word2[j - 1]:\n",
    "                            DP[i][j] = DP[i - 1][j - 1]\n",
    "                        else:\n",
    "                            DP[i][j] = min(DP[i - 1][j], DP[i][j - 1], DP[i - 1][j - 1]) + 1\n",
    "        return DP[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1, word2):\n",
    "        \"\"\"\n",
    "        :type word1: str\n",
    "        :type word2: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        m = len(word1)\n",
    "        n = len(word2)\n",
    "        dp = [[0 for i in range(n+1)] for j in range(m+1)]\n",
    "        for i in range(m+1):\n",
    "            dp[i][0] = i\n",
    "        for j in range(n+1):\n",
    "            dp[0][j] = j\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                if word1[i-1] == word2[j-1]:\n",
    "                    dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j]+1, dp[i][j-1]+1))\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j-1]+1, min(dp[i-1][j]+1, dp[i][j-1]+1))\n",
    "        return dp[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        n = len(word1)\n",
    "        m = len(word2)\n",
    "\n",
    "        MAX_INT = 2**31-1\n",
    "        dp = [[MAX_INT for i in range(m+1)] for j in range(n+1)]\n",
    "        #初始化比较麻烦\n",
    "        for i in range(n+1):\n",
    "            dp[i][0] = i       \n",
    "        for j in range(m+1):\n",
    "            dp[0][j] = j \n",
    "            \n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, m+1): \n",
    "                if word1[i-1] == word2[j-1]: # i, j 是长度， 对应下标减一\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = min(min(dp[i][j-1], dp[i-1][j]), dp[i-1][j-1]) + 1\n",
    "        return dp[n][m]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1, word2):\n",
    "        \"\"\"\n",
    "        :type word1: str\n",
    "        :type word2: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        dp = []\n",
    "        for i in range(len(word1) + 1):\n",
    "            dp.append([0] * (len(word2) + 1))\n",
    "        \n",
    "        for i in range(len(word2) + 1):\n",
    "            dp[0][i] = i\n",
    "        \n",
    "        for i in range(len(word1) + 1):\n",
    "            dp[i][0] = i\n",
    "        \n",
    "        for i in range(1, len(word1) + 1):\n",
    "            for j in range(1, len(word2) + 1):\n",
    "                if word1[i - 1] == word2[j - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j - 1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1\n",
    "        \n",
    "        return dp[-1][-1]\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1, word2):\n",
    "        \"\"\"\n",
    "        :type word1: str\n",
    "        :type word2: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if(word1 == \"\"):\n",
    "            return len(word2)\n",
    "        if(word2 == \"\"):\n",
    "            return len(word1)\n",
    "        table = []\n",
    "        for i in range(len(word1)+1):\n",
    "            table.append([])\n",
    "            for j in range(len(word2)+1):\n",
    "                table[i].append(0)\n",
    "        for i in range(1,len(word1)+1):\n",
    "            table[i][0] = i\n",
    "        for i in range(1,len(word2)+1):\n",
    "            table[0][i] = i\n",
    "        self.getValue(word1,word2,table,len(word1), len(word2))\n",
    "        return table[len(word1)][len(word2)]\n",
    "        \n",
    "    def getValue(self, word1, word2, table, i, j):\n",
    "        if i == 0 and j == 0:\n",
    "            return 0\n",
    "        if(table[i][j-1] == 0):\n",
    "            self.getValue(word1,word2,table,i,j-1)\n",
    "        if(table[i-1][j] == 0):\n",
    "            self.getValue(word1,word2,table,i-1,j)\n",
    "        if(table[i-1][j-1] == 0):\n",
    "            self.getValue(word1,word2,table,i-1,j-1)\n",
    "        value = table[i-1][j-1]\n",
    "        if(word1[i-1] != word2[j-1]):\n",
    "            value=value+1\n",
    "        table[i][j] = min(table[i][j-1]+1,min(table[i-1][j]+1, value))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1, word2):\n",
    "        \"\"\"\n",
    "        :type word1: str\n",
    "        :type word2: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        m, n = len(word1), len(word2)\n",
    "        distance = [[0]*(n+1) for i in range(m+1)]\n",
    "        \n",
    "        for i in range(m+1):\n",
    "            distance[i][0] = i\n",
    "        for i in range(n+1):\n",
    "            distance[0][i] = i\n",
    "        \n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                if word1[i-1] == word2[j-1]:\n",
    "                    distance[i][j] = distance[i-1][j-1]\n",
    "                else:\n",
    "                    dist = min(distance[i-1][j], distance[i][j-1])\n",
    "                    distance[i][j] = min(distance[i-1][j-1], dist)+1\n",
    "        return distance[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1, word2):\n",
    "        \"\"\"\n",
    "        :type word1: str\n",
    "        :type word2: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        a = len(word1)+1\n",
    "        b = len(word2)+1\n",
    "        res = []\n",
    "\n",
    "        for i in range(a):\n",
    "            res.append([])\n",
    "            for j in range(b):\n",
    "                res[i].append(0)\n",
    "\n",
    "        for i in range(a):\n",
    "            res[i][0] = i\n",
    "        for j in range(b):\n",
    "            res[0][j] = j\n",
    "\n",
    "        for i in range(1, a):\n",
    "            for j in range(1, b):\n",
    "                if word1[i-1] == word2[j-1]:\n",
    "                    res[i][j] = res[i-1][j-1]\n",
    "                else:\n",
    "                    res[i][j] = min(res[i][j-1]+1, res[i-1][j]+1, res[i-1][j-1]+1)\n",
    "\n",
    "        return res[a-1][b-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        len_word1 = len(word1)\n",
    "        len_word2 = len(word2)\n",
    "        if len_word1 == 0 or len_word2 == 0:\n",
    "            return len_word1 + len_word2\n",
    "        DP = [[0]*(len_word2+1) for _ in range(2)]\n",
    "        for j in range(len_word2+1):\n",
    "            DP[0][j] = j\n",
    "        for i in range(1,len_word1+1):\n",
    "            index_i = i%2\n",
    "            DP[index_i][0] = i\n",
    "            for j in range(1,len_word2+1):\n",
    "                if word1[i-1] == word2[j-1]:\n",
    "                    DP[index_i][j] = DP[index_i-1][j-1]\n",
    "                else:\n",
    "                    DP[index_i][j] = min(DP[index_i-1][j]+1,DP[index_i][j-1]+1,DP[index_i-1][j-1]+1)\n",
    "        return DP[index_i][len_word2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "        def minDistance(self, s1: str, s2: str) -> int:\n",
    "            len1 = len(s1)\n",
    "            len2 = len(s2)\n",
    "            # 将列初始化\n",
    "            dp = [i for i in range(0, len2+1)]\n",
    "            for i in range(1, len1+1):\n",
    "                # 记录下上一行左上角的值，否则会被覆盖\n",
    "                old = dp[0]\n",
    "                # 将行初始化\n",
    "                dp[0] = i\n",
    "                for j in range(1, len2+1):\n",
    "                    # 记录现在的dp[j]，它是下一个dp[j]的左上角\n",
    "                    temp_old = dp[j]\n",
    "                    if s1[i-1] == s2[j-1]:\n",
    "                        dp[j] = old\n",
    "                    else:\n",
    "                        dp[j] = min(\n",
    "                            dp[j] + 1,\n",
    "                            dp[j-1] + 1,\n",
    "                            old + 1 # 比较的时候也不要忘了\n",
    "                        )\n",
    "                    old = temp_old\n",
    "            return dp[len2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        f = [i for i in range(len(word2) + 1)]\n",
    "        for i in range(len(word1)):\n",
    "            pre = f[0]\n",
    "            f[0] = i+1\n",
    "            for j in range(len(word2)):\n",
    "                x, y = i+1, j+1\n",
    "                temp = pre\n",
    "                pre = f[y]\n",
    "                if word1[i] == word2[j]:\n",
    "                    f[y] = temp\n",
    "                else:\n",
    "                    f[y] = min(temp, f[y], f[y-1]) + 1\n",
    "        return f[len(word2)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "\n",
    "        sz1, sz2 = len(word1), len(word2)\n",
    "        # dp[i][j]表示从word1[0:i]转移到word2[0:j]  数组/字符串切片代表前闭后开\n",
    "        # 比如dp[1][1]表示的是从word1第一个字母转移到word2第1个字母\n",
    "        dp = [[0]*(sz2+1) for i in range(2)]\n",
    "        for j in range(sz2+1):\n",
    "            dp[0][j] = j # word1添加i个字母\n",
    "        for i in range(1, sz1+1):\n",
    "            for j in range(sz2+1):\n",
    "                if j == 0:\n",
    "                    dp[1][j] = i\n",
    "                    continue\n",
    "                if word1[i-1] == word2[j-1]:\n",
    "                    dp[1][j] = dp[0][j-1]\n",
    "                else:\n",
    "                    dp[1][j] = min(min(dp[0][j], dp[1][j-1]), dp[0][j-1])+1\n",
    "            # dp[0] = dp[1] # 不能这么干，会整体引用，产生干扰\n",
    "            for i in range(sz2+1):\n",
    "                dp[0][i] = dp[1][i]\n",
    "        return dp[0][sz2]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        # 状态 dp[i][j]是word1[:i]到word2[:j]的编辑距离\n",
    "        # 递推式:\n",
    "        # if word1[i] == word2[j]: dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]+1, dp[i][j-1]+1)\n",
    "        # if word1[i] != word2[j]: dp[i][j] = min(dp[i-1][j-1]+1, dp[i-1][j]+1, dp[i][j-1]+1)\n",
    "        # 初始值:\n",
    "        # all set 0\n",
    "        # dp[i][0] = dp[i-1][0] + 1\n",
    "        # dp[0][j] = dp[0][j-1] + 1\n",
    "        if not word1 and not word2:\n",
    "            return 0\n",
    "        if not word1 or not word2:\n",
    "            return 1\n",
    "\n",
    "        m, n = len(word1) + 1, len(word2) + 1\n",
    "        # 初始值\n",
    "        dp = [0] * m\n",
    "        for j in range(m):\n",
    "            dp[j] = j\n",
    "        dp_new = [0] * m      \n",
    "        for i in range(1, n):\n",
    "            dp_new[0] = i\n",
    "            for j in range(1, m):\n",
    "                # print(f\"比较{word2[i]}和{word1[j]}\")\n",
    "                # print(f\"比较 {i,j}\")\n",
    "                if word2[i-1] == word1[j-1]:\n",
    "                     dp_new[j] = min(dp[j-1], dp[j]+1, dp_new[j-1]+1)\n",
    "                else:\n",
    "                     dp_new[j] = min(dp[j-1]+1, dp[j]+1, dp_new[j-1]+1)\n",
    "            dp, dp_new = dp_new, dp\n",
    "                # for x in dp:\n",
    "                #     print(x)\n",
    "        \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\r\n",
    "        # 阅读学习\r\n",
    "        # m, n = len(word1), len(word2)\r\n",
    "        # if n * m == 0:\r\n",
    "        #     return n + m\r\n",
    "        \r\n",
    "        # dp = [[0] * (m + 1) for _ in range(n + 1)]\r\n",
    "        # for i in range(m + 1):\r\n",
    "        #     dp[0][i] = i\r\n",
    "        # for j in range(n + 1):\r\n",
    "        #     dp[j][0] = j\r\n",
    "\r\n",
    "        # for i in range(1, m + 1):\r\n",
    "        #     for j in range(1, n + 1):\r\n",
    "        #         lft = dp[j][i - 1] + 1\r\n",
    "        #         down = dp[j - 1][i] + 1\r\n",
    "        #         lft_down = dp[j - 1][i - 1]\r\n",
    "        #         if (word1[i - 1] != word2[j - 1]):\r\n",
    "        #             lft_down += 1\r\n",
    "        #         dp[j][i] = min(lft, down, lft_down)\r\n",
    "        \r\n",
    "        # return dp[-1][-1]\r\n",
    "\r\n",
    "\r\n",
    "        # 自己进阶，修改为滚动数组\r\n",
    "        m, n = len(word1), len(word2)\r\n",
    "        if m * n == 0:\r\n",
    "            return m + n\r\n",
    "        \r\n",
    "        if m < n:\r\n",
    "            word1, word2 = word2, word1\r\n",
    "\r\n",
    "        row, col = len(word1), len(word2)\r\n",
    "\r\n",
    "        dp = list(range(col + 1))\r\n",
    "\r\n",
    "        for i in range(row):\r\n",
    "            lu = dp[0]\r\n",
    "            dp[0] = i + 1\r\n",
    "            for j in range(col):\r\n",
    "                dp[j + 1], lu = min(dp[j] + 1, dp[j + 1] + 1, lu + int(word1[i] != word2[j])), dp[j + 1]\r\n",
    "\r\n",
    "        return dp[-1]\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "  \n",
    "\n",
    "class Solution:\n",
    "    \n",
    "\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        return self._minDistance(word1, word2, 0, 0, max(len(word1), len(word2)))\n",
    "    \n",
    "    @functools.lru_cache\n",
    "    def _minDistance(self, word1: str, word2: str, i1: int, i2: int, inf: int) -> int:\n",
    "        '''\n",
    "        :params i1: word1 index\n",
    "        :params i2: word2 index\n",
    "        :params inf: 极端情况下的结果，避免无必要的递归\n",
    "        '''\n",
    "        # print(word1, word2, i1, i2, inf)\n",
    "        if i2 == len(word2):\n",
    "            return len(word1[i1:])\n",
    "        elif i1 == len(word1):\n",
    "            return len(word2[i2:])\n",
    "        \n",
    "        if word1[i1] == word2[i2]:\n",
    "            # pass\n",
    "            return self._minDistance(word1, word2, i1+1, i2+1, max(len(word1) - (i1+1),  len(word2) - (i2+1))) \n",
    "        \n",
    "        # 替换\n",
    "        ret3 = 1 + self._minDistance(word1, word2, i1+1, i2+1, max(len(word1) - (i1+1),  len(word2) - (i2+1)))\n",
    "        # 插入\n",
    "        ret1 = 1 + self._minDistance(word1, word2, i1, i2+1, max(len(word1) - i1,  len(word2) - (i2+1)))\n",
    "        # 删除\n",
    "        ret2 = 1 + self._minDistance(word1, word2, i1+1, i2, max(len(word1) - (i1+1),  len(word2) - i2))\n",
    "    \n",
    "        \n",
    "        return min(ret1, ret2, ret3, inf)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        @lru_cache\n",
    "        def dfs(i, j):\n",
    "            if i == len(word1): return len(word2) - j\n",
    "            if j == len(word2): return len(word1) - i\n",
    "            if word1[i] == word2[j]:\n",
    "                return dfs(i+1, j+1)\n",
    "            return 1+min(dfs(i+1, j+1), dfs(i+1, j), dfs(i, j+1))\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        m=len(word1)\n",
    "        n=len(word2)\n",
    "        dp=list(range(n+1))\n",
    "        for i in range(m):\n",
    "            lu=dp[0]\n",
    "            dp[0]=i+1\n",
    "            for j in range(n):\n",
    "                dp[j+1],lu=min(dp[j]+1,dp[j+1]+1,lu+int(word1[i]!=word2[j])),dp[j+1]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        # recursion base: \"\" -> \"\": 0\n",
    "        # recursion base: \"xxx\" -> \"\": len(\"xxx\"), f(m, 0) = m, f(0, n) = n\n",
    "        # transformation equation:\n",
    "        # case 1: match => f(m, n) = f(m - 1, n - 1)\n",
    "        # case 2: not match => f(m, n) = min(f(m - 1, n), f(m, n - 1), f(m - 1, n - 1)) + 1\n",
    "        n, m = len(word1), len(word2)\n",
    "        prev = list(range(m + 1))\n",
    "        curr = [0] * (m + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            curr[0] = i\n",
    "            for j in range(1, m + 1):\n",
    "                if word1[i - 1] == word2[j - 1]:\n",
    "                    curr[j] = prev[j - 1]\n",
    "                else:\n",
    "                    curr[j] = 1 + min(curr[j - 1], prev[j], prev[j - 1])\n",
    "            curr, prev = prev, curr\n",
    "        return prev[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        seen = set()\n",
    "        p = [(word1,word2,0)]\n",
    "        while True:\n",
    "            w1,w2,val = p.pop(0)\n",
    "            if (w1,w2) in seen:\n",
    "                continue\n",
    "            if w1 == w2:\n",
    "                return val\n",
    "            seen.add((w1,w2))\n",
    "            while w1 and w2 and w1[0]==w2[0]:\n",
    "                w1,w2 = w1[1:],w2[1:]\n",
    "            val += 1\n",
    "            p += [(w1[1:],w2,val),(w1,w2[1:],val),(w1[1:],w2[1:],val)]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        w1, w2, opened = word1, word2, set()\n",
    "        topens = collections.deque([(w1, w2, 0)])\n",
    "        while True:\n",
    "            w1, w2, value = topens.popleft()\n",
    "            if (w1, w2) in opened:\n",
    "                continue\n",
    "            if w1 == w2:\n",
    "                return value\n",
    "            opened.add((w1, w2))\n",
    "            while w1 and w2 and w1[0] == w2[0]:\n",
    "                w1, w2 = w1[1:], w2[1:]\n",
    "            value += 1\n",
    "            # w1中删除即删除，w2中删除一个字符相当于在w1中添加一个字符，各删一个字符相当于替换\n",
    "            topens += [(w1[1:],w2,value), (w1,w2[1:],value), (w1[1:],w2[1:],value)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        n = len(word2)\n",
    "        f = list(range(n + 1))\n",
    "\n",
    "        for i, x in enumerate(word1):\n",
    "            pre = f[0]\n",
    "            f[0] = i + 1\n",
    "            for j, y in enumerate(word2):\n",
    "                tmp = f[j + 1]\n",
    "                if x == y:\n",
    "                    f[j + 1] = pre\n",
    "                else:\n",
    "                    f[j + 1] = min(f[j], f[j + 1], pre) + 1\n",
    "                pre = tmp    \n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        m, n = len(word1), len(word2)\n",
    "        if word1 == word2: return 0\n",
    "        #if n <= 1 or m <= 1: return max(m, n)\n",
    "        dp = [i for i in range(n+1)]\n",
    "        for i in range(1, m+1):\n",
    "            new_dp = dp[:]\n",
    "            new_dp[0] += 1\n",
    "            for j in range(1, n+1):\n",
    "                if word1[i-1] != word2[j-1]:\n",
    "                    new_dp[j] = min(dp[j-1], new_dp[j-1], dp[j])+1\n",
    "                else:\n",
    "                    new_dp[j] = dp[j-1]\n",
    "            dp = new_dp\n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, s: str, t: str) -> int:\n",
    "        f = list(range(len(t) + 1))\n",
    "\n",
    "        for x in s:\n",
    "\n",
    "            pre = f[0]\n",
    "\n",
    "            f[0] += 1\n",
    "\n",
    "            for j, y in enumerate(t):\n",
    "\n",
    "                tmp = f[j + 1]\n",
    "\n",
    "                f[j + 1] = pre if x == y else min(f[j + 1], f[j], pre) + 1\n",
    "\n",
    "                pre = tmp\n",
    "\n",
    "        return f[-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        seen = set()\n",
    "        p = [(word1, word2, 0)]\n",
    "        while True:\n",
    "            w1, w2, val = p.pop(0)\n",
    "            if (w1, w2) in seen:\n",
    "                continue\n",
    "            if w1 == w2:\n",
    "                return val\n",
    "            seen.add((w1, w2))\n",
    "            while w1 and w2 and w1[0] == w2[0]:\n",
    "                w1, w2 = w1[1:], w2[1:]\n",
    "            val += 1\n",
    "            p += [(w1[1:], w2, val), (w1, w2[1:], val), (w1[1:], w2[1:], val)]\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        m, n = len(word1), len(word2)\n",
    "        @lru_cache\n",
    "        def dfs(i, j):\n",
    "            if i == -1 or j == -1:\n",
    "                return abs(i - j)\n",
    "            # 把str1[0, i] 转换成str2[0, j] 的最小操作数\n",
    "            if word1[i] == word2[j]:\n",
    "                return dfs(i - 1, j - 1)\n",
    "            else:\n",
    "                tmp = 1 + dfs(i - 1, j - 1)\n",
    "                for k in range(0, j):\n",
    "                    if word1[i] == word2[k]:\n",
    "                        tmp = min(tmp, dfs(i - 1, k - 1) + j - k)\n",
    "                for k in range(0, i):\n",
    "                    if word1[k] == word2[j]:\n",
    "                        tmp = min(tmp, dfs(k - 1, j - 1) + i - k)\n",
    "                return tmp\n",
    "              \n",
    "            # efgae\n",
    "            # eaaea  \n",
    "        return dfs(m - 1, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        if len(word1) == 0:\n",
    "            return len(word2)\n",
    "        elif len(word2) == 0:\n",
    "            return len(word1)\n",
    "        elif word1[0] == word2[0]:\n",
    "            return self.minDistance(word1[1:], word2[1:])\n",
    "        else:\n",
    "            return min(self.minDistance(word1[1:], word2[1:]) + 1, self.minDistance(word1[1:], word2) + 1, self.minDistance(word1, word2[1:]) + 1)        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    from functools import lru_cache\n",
    "# maxsize 是指定最大缓存多少个调用，默认为 128，如果设置为 None 则关闭缓存功能\n",
    "# typed 是指定参数值相同但类型不同时是否单独缓存，默认值为 False\n",
    "    @lru_cache(maxsize=100, typed=False)\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        if len(word1) == 0:\n",
    "            return len(word2)\n",
    "        elif len(word2) == 0:\n",
    "            return len(word1)\n",
    "        elif word1[0] == word2[0]:\n",
    "            return self.minDistance(word1[1:], word2[1:])\n",
    "        else:\n",
    "            return min(self.minDistance(word1[1:], word2[1:]) + 1, self.minDistance(word1[1:], word2) + 1, self.minDistance(word1, word2[1:]) + 1)        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        mem = {}\n",
    "\n",
    "        def find(word1, word2, i, j):\n",
    "            nonlocal mem\n",
    "\n",
    "            if i < 0:\n",
    "                return j + 1\n",
    "            \n",
    "            if j < 0:\n",
    "                return i + 1\n",
    "            \n",
    "            if i not in mem:\n",
    "                mem[i] = {}\n",
    "            \n",
    "            if j in mem[i]:\n",
    "                return mem[i][j]\n",
    "\n",
    "            if word1[i] == word2[j]:\n",
    "                mem[i][j] = find(word1, word2, i - 1, j - 1)\n",
    "                return mem[i][j]\n",
    "            else:\n",
    "                mem[i][j] = min(find(word1, word2, i - 1, j) + 1, find(word1, word2, i, j - 1) + 1, find(word1, word2, i - 1, j - 1) + 1)\n",
    "                return mem[i][j]\n",
    "        \n",
    "        return find(word1, word2, len(word1) - 1, len(word2) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        m, n = len(word1), len(word2)\n",
    "        @lru_cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i == -1 or j == -1:\n",
    "                return abs(j - i)\n",
    "            if word1[i] == word2[j]:\n",
    "                return dfs(i - 1, j - 1)\n",
    "            return 1 + min(dfs(i - 1, j), dfs(i, j - 1), dfs(i - 1, j - 1))\n",
    "        return dfs(m - 1, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        if len(word1) == 0 or len(word2) == 0:\n",
    "            return max(len(word1), len(word2))\n",
    "        if word1[0] == word2[0]:\n",
    "            return self.minDistance(word1[1:], word2[1:])\n",
    "        a = self.minDistance(word1[1:], word2)\n",
    "        b = self.minDistance(word1, word2[1:])\n",
    "        c = self.minDistance(word1[1:], word2[1:])\n",
    "        return min(a,b,c) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        memo = {}\n",
    "\n",
    "        def backtracking(i, j): \n",
    "            if (i, j) in memo: return memo[(i, j)]\n",
    "            if i == -1 and j == -1: \n",
    "                return 0\n",
    "            elif i == -1: \n",
    "                return j + 1\n",
    "            elif j == -1: \n",
    "                return i + 1\n",
    "            \n",
    "            if word1[i] == word2[j]: \n",
    "                return backtracking(i - 1, j - 1)\n",
    "            else: \n",
    "                # choice 1: replace word 1 letter\n",
    "                op1 = backtracking(i - 1, j - 1) + 1\n",
    "\n",
    "                # choice 2: delete word 1 letter\n",
    "                op2 = backtracking(i - 1, j) + 1\n",
    "\n",
    "                # choice 3: insert letter to word 1\n",
    "                op3 = backtracking(i, j - 1) + 1\n",
    "\n",
    "                memo[(i, j)] = min(op1, op2, op3)\n",
    "                return memo[(i, j)]\n",
    "\n",
    "        return backtracking(len(word1) - 1, len(word2) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, s: str, t: str) -> int:\n",
    "        n, m = len(s), len(t)\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i < 0: return j + 1\n",
    "            if j < 0: return i + 1\n",
    "            if s[i] == t[j]: return dfs(i - 1, j - 1)\n",
    "            return min(dfs(i - 1, j), dfs(i, j - 1), dfs(i - 1, j - 1)) + 1\n",
    "        return dfs(n - 1, m - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        n,m=len(word1),len(word2)\n",
    "        @cache\n",
    "        def aiv(s1,s2):\n",
    "            if s1<0:\n",
    "                return s2+1\n",
    "            if s2<0:\n",
    "                return s1+1\n",
    "            if word1[s1]==word2[s2]:\n",
    "                return aiv(s1-1,s2-1)\n",
    "            return min(aiv(s1-1,s2),aiv(s1,s2-1),aiv(s1-1,s2-1))+1\n",
    "        return aiv(n-1,m-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        def dp(i, j):\n",
    "            if i == -1:\n",
    "                return j+1\n",
    "            if j == -1:\n",
    "                return i+1\n",
    "            if memo[i][j] != -1:\n",
    "                return memo[i][j]\n",
    "            if word1[i] == word2[j]:\n",
    "                memo[i][j] = dp(i-1, j-1)\n",
    "            else:\n",
    "                memo[i][j] = min(dp(i-1, j), min(dp(i, j-1), dp(i-1, j-1)))+1\n",
    "            return memo[i][j]\n",
    "\n",
    "        m, n = len(word1), len(word2)\n",
    "        memo =[[-1 for _ in range(n)] for _ in range(m)]\n",
    "        return dp(m-1, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        if len(word1) ==0 or len(word2) == 0:\n",
    "            return max(len(word1), len(word2))\n",
    "        \n",
    "        dp = [[0]* ((len(word2)) + 1) for _ in range(len(word1)+1)]\n",
    "\n",
    "        for i in range(1,len(word2)+1):\n",
    "            dp[0][i] = i\n",
    "        for j in range(1,len(word1)+1):\n",
    "            dp[j][0] = j\n",
    "\n",
    "        for j in range(1,len(word2) + 1):\n",
    "            for i in range(1, len(word1) +1):\n",
    "                if word1[i-1] == word2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        n1, n2 = len(word1), len(word2)\n",
    "\n",
    "        # Initialize a matrix to store the edit distance\n",
    "        dp = [[0] * (n2 + 1) for _ in range(n1 + 1)]\n",
    "\n",
    "        # Fill the matrix with edit distance values\n",
    "        for i in range(n1 + 1):\n",
    "            for j in range(n2 + 1):\n",
    "                if i == 0:\n",
    "                    dp[i][j] = j\n",
    "                elif j == 0:\n",
    "                    dp[i][j] = i\n",
    "                elif word1[i - 1] == word2[j - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j - 1]\n",
    "                else:\n",
    "                    dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])\n",
    "\n",
    "        return dp[n1][n2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "\n",
    "        print(len(word1), len(word2))\n",
    "        #dp = [[0]*(len(word2)+1)]*(len(word1)+1) 列表拷贝\n",
    "        dp = [[0]*(len(word2)+1) for i in range(len(word1)+1)]\n",
    "        print(dp)\n",
    "        for i in range(len(word1)+1):dp[i][0]=i\n",
    "        print(dp)\n",
    "        for j in range(len(word2)+1):dp[0][j]=j\n",
    "        print(dp)\n",
    "\n",
    "        for i in range(1,len(word1)+1):\n",
    "            for j in range(1,len(word2)+1):\n",
    "                if word1[i-1] == word2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1\n",
    "                    print(i,j, dp[i][j])\n",
    "        return dp[i][j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        n,m=len(word1),len(word2)\n",
    "        if n==0:\n",
    "            return m\n",
    "        if m==0:\n",
    "            return n\n",
    "        dp=[[-1 for _ in range(max(n,m))]for _ in range(max(m,n))]\n",
    "        def method(i,j):\n",
    "            if j==m:\n",
    "                return len(word1[i:])\n",
    "            if i==n:\n",
    "                return len(word2[j:])\n",
    "            if dp[i][j]!=-1:\n",
    "                return dp[i][j]\n",
    "            # if i==n-1:\n",
    "            #     a=len(word2[j+1:]) if word1[i]==word2[j] else len(word2[j:])\n",
    "            #     return a\n",
    "            # else:\n",
    "            if word1[i]==word2[j]:\n",
    "                res=min(method(i+1,j+1),1+method(i,j+1),1+method(i+1,j))   #顺移 插入 删除\n",
    "            else:\n",
    "                res=min(1+method(i,j+1),1+method(i+1,j),1+method(i+1,j+1))  #插入 删除 替换\n",
    "            dp[i][j]=res\n",
    "            return res\n",
    "        return method(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        m = len(word1)\n",
    "        n = len(word2)\n",
    "        dp = [[max(i, j) for j in range(n+1)] for i in range(m+1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if word1[i]==word2[j]:\n",
    "                    dp[i+1][j+1] = min(dp[i][j], dp[i+1][j+1])\n",
    "                dp[i+1][j+1] =min(dp[i+1][j+1], min(dp[i][j+1], dp[i][j], dp[i+1][j]) + 1)\n",
    "        return dp[-1][-1]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        if not word1 and not word2:\n",
    "            return 0\n",
    "        elif not word1:\n",
    "            return len(word2)\n",
    "        elif not word2:\n",
    "            return len(word1)\n",
    "        w1_lst=list(word1)\n",
    "        w2_lst=list(word2)\n",
    "\n",
    "        n=len(w1_lst)\n",
    "        m=len(w2_lst)\n",
    "        w1_lst=[0]+w1_lst\n",
    "        w2_lst=[0]+w2_lst\n",
    "\n",
    "        dp=[[501 for j in range(m+1)] for i in range(n+1)] #dp[i][j]表示word1的前缀长度为i的子前缀和word2长度为j的子前缀最少操作数\n",
    "        dp[0][0]=0\n",
    "        for i in range(0,n+1):\n",
    "            dp[i][0]=i\n",
    "            # if w1_lst[i]==w2_lst[1]:\n",
    "            #     dp[i][1]=dp[i-1][0]\n",
    "            # else:\n",
    "            #     dp[i][1]=i\n",
    "            \n",
    "\n",
    "        \n",
    "        for j in range(0,m+1):\n",
    "            dp[0][j]=j\n",
    "            # if w1_lst[1]==w2_lst[j]:\n",
    "            #     dp[1][j]= dp[1][j-1]\n",
    "            # else:\n",
    "            #     dp[1][j]= dp[1][j-1]+1\n",
    "            \n",
    "        \n",
    "\n",
    "        print('dp',dp)\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,m+1):\n",
    "                if w1_lst[i]==w2_lst[j]:\n",
    "                    if i==n and j==m:\n",
    "                        dp[i][j]=min(dp[i][j],dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1])\n",
    "                    elif i==n:\n",
    "                        dp[i][j]=min(dp[i][j],dp[i-1][j]+1,dp[i][j-1]+1,dp[i][j+1]+1,dp[i-1][j-1])\n",
    "                    elif j==m:\n",
    "                        dp[i][j]=min(dp[i][j],dp[i-1][j]+1,dp[i][j-1]+1,dp[i+1][j]+1,dp[i-1][j-1])\n",
    "                    else:\n",
    "                        dp[i][j]=min(dp[i][j],dp[i-1][j]+1,dp[i][j-1]+1,dp[i+1][j]+1,dp[i][j+1]+1,dp[i-1][j-1])\n",
    "\n",
    "\n",
    "                    # dp[i][j]=min(dp[i][j],dp[i-1][j-1])\n",
    "                elif w1_lst[i]!=w2_lst[j]:\n",
    "                    if i==n and j==m:\n",
    "                        dp[i][j]=min(dp[i][j],dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+1)\n",
    "                    elif i==n:\n",
    "                        dp[i][j]=min(dp[i][j],dp[i-1][j]+1,dp[i][j-1]+1,dp[i][j+1]+1,dp[i-1][j-1]+1)\n",
    "                    elif j==m:\n",
    "                        dp[i][j]=min(dp[i][j],dp[i-1][j]+1,dp[i][j-1]+1,dp[i+1][j]+1,dp[i-1][j-1]+1)\n",
    "                    else:\n",
    "                        dp[i][j]=min(dp[i][j],dp[i-1][j]+1,dp[i][j-1]+1,dp[i+1][j]+1,dp[i][j+1]+1,dp[i-1][j-1]+1)\n",
    "        \n",
    "        return dp[n][m]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        dp = [[0 for _ in range(len(word2) + 1)] for _ in range(len(word1) + 1)]\n",
    "\n",
    "        for i in range(1, len(word2) + 1):\n",
    "            dp[0][i] = i\n",
    "        \n",
    "        for i in range(1, len(word1) + 1):\n",
    "            dp[i][0] = i\n",
    "\n",
    "\n",
    "        for i in range(1, len(word1) + 1):\n",
    "            for j in range(1, len(word2) + 1):\n",
    "                if word1[i - 1] == word2[j - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j - 1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1\n",
    "        \n",
    "        print(dp)\n",
    "        return dp[len(word1)][len(word2)]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        len1, len2 = len(word1), len(word2)\n",
    "        dp = [[0 for i in range(len2+1)] for j in range(len1+1)]\n",
    "        for i in range(len1+1):\n",
    "            dp[i][0] = i\n",
    "        for i in range(len2+1):\n",
    "            dp[0][i] = i\n",
    "        for i in range(1, len1+1):\n",
    "            for j in range(1, len2+1):\n",
    "                if word1[i-1] == word2[j-1]:\n",
    "                    dp[i][j] == dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] == min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1\n",
    "        \n",
    "        \n",
    "        \n",
    "        n1 = len(word1)\n",
    "        n2 = len(word2)\n",
    "        dp = [[0] * (n2 + 1) for _ in range(n1 + 1)]\n",
    "        # 第一行\n",
    "        for j in range(1, n2 + 1):\n",
    "            dp[0][j] = dp[0][j-1] + 1\n",
    "        # 第一列\n",
    "        for i in range(1, n1 + 1):\n",
    "            dp[i][0] = dp[i-1][0] + 1\n",
    "        for i in range(1, n1 + 1):\n",
    "            for j in range(1, n2 + 1):\n",
    "                if word1[i-1] == word2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1] ) + 1\n",
    "        #print(dp)      \n",
    "        return dp[-1][-1]\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        n=len(word1)\n",
    "        m=len(word2)\n",
    "        dp=[[i for i in range (m+1)] for j in range(n+1)]\n",
    "        for i in range(n+1):\n",
    "            dp[i][0]=i\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,m+1):\n",
    "                if word1[i-1]==word2[j-1]:\n",
    "                    dp[i][j]=dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+1)\n",
    "        return dp[n][m]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        n1 = len(word1)\n",
    "        n2 = len(word2)\n",
    "        dp = [[0] * (n2 + 1) for _ in range(n1 + 1)]\n",
    "        # 第一行\n",
    "        for j in range(1, n2 + 1):\n",
    "            dp[0][j] = dp[0][j-1] + 1\n",
    "        # 第一列\n",
    "        for i in range(1, n1 + 1):\n",
    "            dp[i][0] = dp[i-1][0] + 1\n",
    "        for i in range(1, n1 + 1):\n",
    "            for j in range(1, n2 + 1):\n",
    "                if word1[i-1] == word2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1] ) + 1\n",
    "        print(dp)      \n",
    "        # [[0, 1, 2, 3],\n",
    "        #  [1, 1, 2, 3],\n",
    "        #  [2, 2, 1, 2],\n",
    "        #  [3, 2, 2, 2],\n",
    "        #  [4, 3, 3, 2],\n",
    "        #  [5, 4, 4, 3]]\n",
    "        return dp[-1][-1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
